package primary.code12_dp;

import lombok.extern.slf4j.Slf4j;

/**
 * “动态规划技巧总结”：1 找到一种暴力递归方法 -> 2 记忆搜索dp -> 3 严格表结构动态规划 -> 4 严格表结构（精）动态规划
 * <p>
 * 暴力递归寻找方法：
 * 1. 从左向右
 * 2. 范围
 * <p>
 * 暴力递归方法评判标准：1 单个变量的维度尽量低；2 变量的数量尽量少；
 * <p>
 * 严格表结构的实现技巧：1 确定变量的范围；2 填充base case；3 确定一般位置的计算方式，确定状态依赖；4 最终结果的计算方式
 * <p>
 * 严格表结构（精）实现技巧：在严格表结构基础上，减少不必要的计算
 */
@Slf4j
public class Code01_Robot {

    /*
     * 长度为 N 的位置（1~N），机器人当前在位置 S, 目标终点 E, 必须行动步数为 K, 请问有几种从 S 到 E 的走法？
     *
     * 暴力递归
     * N 可移动的位置
     * S 起始位置
     * E 终止位置
     * K 剩余必须移动步数
     * */
    public static int findWay1(int N, int S, int E, int K) {
        if (K == 0) {
            return S == E ? 1 : 0;
        }
        if (S == 1) {
            return findWay1(N, S + 1, E, K - 1);
        }
        if (S == N) {
            return findWay1(N, S - 1, E, K - 1);
        }
        return findWay1(N, S + 1, E, K - 1) + findWay1(N, S - 1, E, K - 1);
    }

    /*
     * 记忆搜索dp(加结果缓存)
     * S 取值范围 1～N
     * K 取值范围 0～K
     * */
    public static int findWay2(int N, int S, int E, int K) {
        int[][] dp = new int[N + 1][K + 1]; // cache
        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= K; j++) {
                dp[i][j] = -1;
            }
        }
        return findWay2(N, S, E, K, dp);
    }

    public static int findWay2(int N, int S, int E, int K, int[][] dp) {
        if (dp[S][K] != -1) {
            return dp[S][K];
        }

        if (K == 0) {
            dp[S][K] = S == E ? 1 : 0;
            return dp[S][K];
        }
        if (S == 1) {
            dp[S][K] = findWay1(N, S + 1, E, K - 1);
            return dp[S][K];
        }
        if (S == N) {
            dp[S][K] = findWay1(N, S - 1, E, K - 1);
            return dp[S][K];
        }
        dp[S][K] = findWay1(N, S + 1, E, K - 1) + findWay1(N, S - 1, E, K - 1);
        return dp[S][K];
    }

    /*
     * 严格表结构
     *
     * N, K 固定不变
     *
     * 变量 S, K 均是一维
     * S 取值范围 1～N
     * K 取值范围 0～K
     * */
    public static int findWay3(int N, int S, int E, int K) {
        // start rest
        int[][] dp = new int[N + 1][K + 1];
        for (int start = 0; start <= N; start++) {
            dp[start][0] = start == E ? 1 : 0;
        }
        for (int rest = 1; rest <= K; rest++) {
            for (int start = 1; start <= N; start++) {
                if (start == 1) {
                    dp[start][rest] = dp[start + 1][rest - 1];
                } else if (start == N) {
                    dp[start][rest] = dp[start - 1][rest - 1];
                } else {
                    dp[start][rest] = dp[start + 1][rest - 1] + dp[start - 1][rest - 1];
                }
            }
        }
        return dp[S][K];
    }


    public static void main(String[] args) {
        int N = 6;
        int S = 2;
        int E = 4;
        int K = 6;
        log.info("暴力递归，计算结果: {}", findWay1(N, S, E, K));
        log.info("记忆搜索DP，计算结果: {}", findWay2(N, S, E, K));
        log.info("严格表结构DP，计算结果: {}", findWay3(N, S, E, K));
    }
}
